#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

#include "Heap.h"

//交换函数
void Swap(DataType* left, DataType* right)
{
    int temp = *left;
    *left = *right;
    *right = temp;  
}

//小堆
int Less(DataType left, DataType right)
{
    return left < right;
}

//大堆
int Greater(DataType left, DataType right)
{
    return left > right;
}


//向下调整函数
//调整的规则:(大堆为例)
//1.选出左右孩子较大的那一个。
//2.大的孩子和父亲比较
//3.若大的孩子比父亲大，则与父亲交换。并且把原来孩子的位置赋给父亲。父亲去找下一个孩子。迭代起来。结束条件是孩子超出了树的结点的大小
//4.若大的孩子比父亲小，就结束迭代。
void AdjustDown(Heap* hp, int parent)
{
    //下面两步是为了找到节点数(即有效元素的个数)，也可以在函数里面直接设置节点的个数的参数
    DataType* array = hp->array;
    int size = hp->size;

    //默认让child标记左孩子，因为parent可能不存在右孩子
    int child = parent * 2  + 1;
    
    while(child < size)
    {
        //右孩子存在的情况下
        //找到左右孩子中最大的，调用函数指针
        if(child + 1 < size && hp->pCom(array[child + 1],array[child]))
            child += 1;


        //如果孩子大于父亲就交换
        if(hp->pCom(array[child], array[parent]))
        {
            Swap(&array[child], &array[parent]);

            //父节点往下移动，可能导致其子树不满足堆的特性
            //往下迭代
            parent = child;
            child = parent * 2 + 1;
        }
        else 
        {
            return;
        }
    }
}


//向上调整(大堆为例)
//1. 选出左右孩子较大的那一个。
//2. 大的孩子和父亲比较
//3. 若大的孩子比父亲大，则与父亲交换。并且把原来孩子的位置赋给父亲。父亲去找下一个孩子。迭代起来。结束条件是孩子超出了树的根节点
//4. 若大的孩子比父亲小，就结束迭代。
void AdjustUp(Heap* hp)
{
    DataType* array = hp->array;
    int child = hp->size - 1;
    int parent = ((child - 1) >> 1);

    while(child)
    {
        if(hp->pCom(array[child], array[parent]))
        {
            Swap(&array[child], &array[parent]);

            //向上迭代
            child = parent;
            parent = ((child - 1) >> 1);
        }
        else 
        {
            return;
        }
    }
}


//初始化(建堆)
void HeapInit(Heap* hp, DataType* array, int size, PCOM pCom)
{
    //定义第一个非叶子节点
    int lastNotLeaf = 0;

    assert(hp);

    //为堆存储值开辟空间
    hp->array = (DataType*)malloc(sizeof(DataType)*size); //array的类型是DataType*,mallco的返回类型也是DataType*
    if(NULL == hp->array)
    {
        assert(0);
        return;
    }

    hp->capacity = size;

    //赋值，将数组的值移动到堆里面
    //memcpy(hp->array, array, sizeof(DataType)*size);
    for(int i = 0; i < size; i++)
    {
        hp->array[i] = array[i];
    }

    hp->size = size;
    hp->pCom = pCom;

    //1. 找倒数第一个非叶子节点
    lastNotLeaf = ((size - 1) - 1) / 2;

    //2. 从该节点开始，逐个往前直到根节点，对遇到的节点应用向下调整
    for(int i = lastNotLeaf; i >= 0; i--)
    {
        AdjustDown(hp, i);
    }
}

//扩容
void CheckCapacity(Heap* hp)
{
    assert(hp);

    if(hp->size == hp->capacity)
    {
        hp->array = (DataType*)realloc(hp->array, sizeof(DataType) * hp->size*2);
        if(NULL == hp->array)
        {
            assert(0);
            return;
        }

        hp->capacity *= 2;
    }
}

//插入
void HeapInsert(Heap* hp, DataType data)
{
    //先检查是否需要扩容，再插入
    CheckCapacity(hp);

    //1. 将元素先插入到最后一个元素之后，再对size加加
    hp->array[hp->size++] = data;

    //2. 新元素插入之后，可能会破坏堆的特性，因此需要调整顺序
    AdjustUp(hp);
}

//删除
void HeapErase(Heap* hp)
{
    //删除的前提是堆里面有元素
    //首先需要判空
    if(HeapEmpty(hp))
        return;

    //1. 将堆顶元素与堆中最后一个元素进行交换
    Swap(&hp->array[0], &hp->array[hp->size - 1]);

    //2. 将堆中有效元素的个数-1
    hp->size -= 1;

    //3. 将剩余的元素进行调整
    AdjustDown(hp,0); //从根节点开始向下调整
}

//获取堆顶元素
DataType HeapTop(Heap* hp)
{
    assert(!HeapEmpty(hp));

    return hp->array[0];
}

//判空
int HeapEmpty(Heap* hp)
{
    assert(hp);

    return 0 == hp->size;
}

//获取有效元素的个数
int HeapSize(Heap* hp)
{
    assert(hp);

    return hp->size;
}

//销毁
void HeapDestroy(Heap* hp)
{
    assert(hp);

    if(hp->array)
    {
        free(hp->array);
        hp->array = NULL;
        hp->capacity = 0;
        hp->size = 0;
    }
}
